package tree;

import java.lang.classfile.constantpool.IntegerEntry;
import java.util.*;

class TreeNode {
     int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
public class Solution {
    /*
    给你一个二叉树的根节点 root ， 检查它是否轴对称。
示例 1：
输入：root = [1,2,2,3,4,4,3]
输出：true
示例 2：
输入：root = [1,2,2,null,3,null,3]
输出：false
     */
    public boolean isSymmetric(TreeNode root) {
            return isSame(root.left,root.right);
    }
    public boolean isSame(TreeNode left,TreeNode right){
        if(left==null&&right==null){
            return true;
        }
        if((left==null||right==null)||left.val!=right.val){
            return false;
        }
        return isSame(left.left,right.right)&&isSame(left.right,right.left);
    }
    /*
    给你一棵二叉树的根节点，返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。
示例 1：
输入：root = [1,2,3,4,5]
输出：3
解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。
示例 2：
输入：root = [1,2]
输出：1
     */
    private int max = 0;
    public int diameterOfBinaryTree(TreeNode root) {
            maxDepth(root);
            return max;
    }
    public int maxDepth(TreeNode root){
        if(root == null){
            return 0;
        }
        int leftMax = maxDepth(root.left);
        int rightMax = maxDepth(root.right);
        max = Math.max(leftMax+rightMax,max);
        return Math.max(leftMax,rightMax)+1;
    }
    /*
    给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
示例 2：
输入：root = [1]
输出：[[1]]
示例 3：
输入：root = []
输出：[]
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return new ArrayList<List<Integer>>();
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            List<Integer> l = new ArrayList<>();
            for(int i = 0;i<size;i++){
                TreeNode poll = queue.poll();
                l.add(poll.val);
                if(poll.left!=null){
                    queue.offer(poll.left);
                }
                if(poll.right!=null){
                    queue.offer(poll.right);
                }
            }
            res.add(l);
        }
        return res;
    }
    /*
    给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵
平衡
 二叉搜索树。
示例 1：
输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
     */
    public static TreeNode sortedArrayToBST(int[] nums) {
        int left = 0;
        int right = nums.length-1;
        TreeNode root = new TreeNode();
        return toB(nums,left,right,root);
    }
    public static TreeNode toB(int[]nums,int left,int right,TreeNode root){
        int mid=(left+right)/2;
        if(left>right){
            return root;
        }
        if(root==null){
            root = new TreeNode();
        }
        if(mid<=nums.length-1) {
            root.val = nums[mid];
        }
        root.left = toB(nums,left,mid-1,root.left);
        root.right = toB(nums,mid+1,right,root.right);
        return root;
    }
    /*
    给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
节点的左
子树
只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1：
输入：root = [2,1,3]
输出：true
示例 2：
输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。
     */
    public boolean isValidBST(TreeNode root) {
        if(root == null){
            return true;
        }
        return in(root);
    }
    long m = Long.MIN_VALUE;
    public boolean in(TreeNode root){
        if(root==null){
            return true;
        }
        boolean left = in(root.left);
        if(m<root.val){
            m = (long)root.val;
        }else{
            return false;
        }
        boolean right = in(root.right);
        return left&&right;
    }
    /*
    给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）
示例 1：
输入：root = [3,1,4,null,2], k = 1
输出：1
示例 2：
输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3
     */
    int min = Integer.MAX_VALUE;
    public int kthSmallest(TreeNode root, int k) {
        if(root==null){
            return 0;
        }
        List<Integer> res = new ArrayList<>();
        in(root,res);
        Integer arr[] = res.toArray(new Integer[0]);
        return arr[k-1];
    }
    public void in(TreeNode root,List<Integer> res){
        if(root==null){
            return;
        }
        in(root.left,res);
        res.add(root.val);
        in(root.right,res);
    }
    /*
    给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例 1:
输入: [1,2,3,null,5,null,4]
输出: [1,3,4]
示例 2:
输入: [1,null,3]
输出: [1,3]
示例 3:
输入: []
输出: []
     */
    public static List<Integer> rightSideView(TreeNode root) {
            List<Integer> res = new ArrayList<>();
            if(root == null){
                return new ArrayList<>();
            }
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while(!queue.isEmpty()){
                int size = queue.size();
                for(int i =0;i<size;i++){
                    TreeNode poll = queue.poll();
                    if(i+1==size){
                        res.add(poll.val);
                    }
                    if(poll.left!=null){
                        queue.offer(poll.left);
                    }
                    if (poll.right!=null){
                        queue.offer(poll.right);
                    }
                }
            }
            return res;
    }
    /*
    给你二叉树的根结点 root ，请你将它展开为一个单链表：
展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。
示例 1：
输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [0]
输出：[0]
     */
    public static void flatten(TreeNode root) {
        List<TreeNode> list = new ArrayList<>();
        pre(root,list);
        TreeNode tail = null;
        for (TreeNode node : list) {
            if(root == node){
                tail = root ;
            }else{
                node.left = null;
                root.left=null;
                tail.right = node;
                tail = tail.right;
            }
        }
    }
    public static  void pre(TreeNode root,List<TreeNode> list){
        if(root == null){
            return ;
        }
       list.add(root);
        pre(root.left,list);
        pre(root.right,list);
    }
    /*
    给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
示例 1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]
示例 2:
输入: preorder = [-1], inorder = [-1]
输出: [-1]
     */
    Map<Integer,Integer> tMp = new HashMap<>();
    public  TreeNode buildTree(int[] preorder, int[] inorder) {
//        if(preorder.length==0||inorder.length==0){
//            return null;
//        }
//        TreeNode root = new TreeNode(preorder[0]);
//        for (int i = 0; i < inorder.length; i++) {
//            if (inorder[i] == preorder[0]) {
//                root.left =
//                        buildTree(Arrays.copyOfRange(preorder, 1, i + 1), Arrays.copyOfRange(inorder, 0, i));
//                root.right =
//                        buildTree(Arrays.copyOfRange(preorder, i + 1, preorder.length), Arrays.copyOfRange(inorder, i + 1, inorder.length));
//
//            }
//        }
//        return root;
        for(int i = 0;i<preorder.length;i++){
            tMp.put(inorder[i],i);
        }
        return buildSubTree(0,preorder.length-1,preorder,0,inorder.length-1,inorder);

}
public TreeNode buildSubTree(int preLeft,int preRight,int [] preorder,int inLeft , int inRight,int[] inorder){
    if (preLeft > preRight) {
        return null;
    }
    //先序遍历确定根结点
    int rootVal = preorder[preLeft];
    TreeNode root = new TreeNode(rootVal);
    Integer midIndex = tMp.get(rootVal);
    int leftLen = midIndex-inLeft;
    root.left = buildSubTree(preLeft+1,leftLen+preLeft,preorder,inLeft,midIndex-1,inorder);
    root.right = buildSubTree(leftLen+preLeft+1,preRight,preorder,midIndex+1,inRight,inorder);
    return root;
}
/*
给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
示例 1：
输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。
示例 2：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：3
 */
    int count = 0;
    Map<Long, Integer> premix = new HashMap<>();
public int pathSum(TreeNode root, int targetSum) {
    premix.put(0L,1);
    long cur = 0;
    premix(root,cur,targetSum);
    return count;
}
public int premix(TreeNode root,long cur,long target){
    if(root == null){
        return 0;
    }
   int res = 0;
   cur+=root.val;
   res = premix.getOrDefault(cur-target,0);
   premix.put(cur,premix.getOrDefault(cur,0)+1);
   res+=premix(root.left,cur,target);
   res+=premix(root.right,cur,target);
   premix.put(cur,premix.getOrDefault(cur,0)-1);
   return res;
}
/*
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
示例 2：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3：
输入：root = [1,2], p = 1, q = 2
输出：1
 */
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//    if (root == null) {
//        return root;
//    }
//    List<TreeNode> p_list = new ArrayList<>();
//    List<TreeNode> q_list = new ArrayList<>();
//    getParent(root, p, p_list);
//    getParent(root, q, q_list);
//    TreeNode parent = null;
//    for(int i = 0;i<p_list.size();i++){
//        for(int j = 0;j< q_list.size();j++){
//            if(p_list.get(i)==q_list.get(j)){
//                parent = p_list.get(i);
//                break;
//            }
//        }
//        if(parent!=null){
//            break;
//        }
//    }
//    return parent;
    if(root==null){
        return  root;
    }
    if(root==p||root==q){
        return root;
    }
    TreeNode left = lowestCommonAncestor(root.left,p,q);
    TreeNode right = lowestCommonAncestor(root.right,p,q);
    if(left==null){
        return right;
    }else if(right==null){
        return left;
    }else if(left==null&&right==null){
        return null;
    }else{
        return root;
    }
}
public boolean getParent(TreeNode root,TreeNode node,List<TreeNode> res){
    if(root == null){
        return false;
    }
    if(root == node){
        res.add(root);
        return true;
    }
    if(getParent( root.left,node, res)||getParent(root.right,node,res)){
        res.add(root);
        return true;
    }
    return false;
}
/*
二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
示例 1：
输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6
示例 2：
输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42
 */
    int path = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
        roadSum(root);
        return path;
}
public int roadSum(TreeNode root){
    if(root==null){
        return 0;
    }
    path = Math.max(root.val,path);
    //左边的路径小于0，置为0
    int maxLeftVal = Math.max(0,roadSum(root.left));
    //同理
    int maxRightVal = Math.max(0,roadSum(root.right));
    path = Math.max(maxLeftVal+maxRightVal+root.val,path);
    return Math.max(maxLeftVal,maxRightVal)+root.val;
}
}
class Test{
    public static void main(String[] args) {
        TreeNode tree = new TreeNode(1);
        tree.left = new TreeNode(4);
        tree.right = new TreeNode(5);
        tree.left.right=new TreeNode(4);
        tree.left.left = new TreeNode(4);
        tree.right.right =  new TreeNode(5);
        Solution solution = new Solution();
       
    }
}
